package com.duojuhe.common.utils.tree;


import java.util.*;

/**
 * tree结构工具类
 *
 * eavan
 *
 * @date 2018/5/25.
 */
public class TreeUtil<T> extends TreeBaseBean {

    /**
     * tree转成list
     * @param treeList
     * @param <T>
     * @return
     */
    public static <T> List<TreeBaseBean> treeToList(List<TreeBaseBean>  treeList) {
        List<TreeBaseBean> list = new ArrayList<>();
        for (TreeBaseBean tree : treeList) {
            List<TreeBaseBean> child = tree.getChildren();
            list.add(tree);
            if (child != null && child.size() > 0) {
                list.addAll(treeToList(child));
                tree.setChildren(null);
            }
        }
        return list;
    }

    /**
     * 没有指定根节点时 创建树形结构数据
     * @param allList
     * @return
     */
    public static List<TreeBaseBean> treeList(List<? extends TreeBaseBean> allList){
        Map<String, List<TreeBaseBean>> map = new HashMap<String, List<TreeBaseBean>>();
        List<TreeBaseBean> baseBeanList = new ArrayList<TreeBaseBean>();
        HashSet<String> tempSet = new HashSet<>();
        for (TreeBaseBean t : allList){
            baseBeanList.add(t);
            tempSet.add(t.getId());
            String key = t.getParentId();
            if(map.containsKey(key)) {
                map.get(key).add(t);
            } else {
                List<TreeBaseBean> mapValue = new ArrayList<TreeBaseBean>();
                mapValue.add(t);
                map.put(key, mapValue);
            }
        }
        List<TreeBaseBean> treeList = new ArrayList<>();

        HashSet<String> querySet = new HashSet<>();
        for(TreeBaseBean t : allList) {
            // 如果是顶级节点, 遍历该父节点的所有子节点
            String parentId = t.getParentId();
            if (!tempSet.contains(parentId)&&!querySet.contains(parentId)){
                List<TreeBaseBean> tree = map.get(parentId);
                querySet.add(parentId);
                treeList.addAll(tree);
            }
        }
        recursionToTree(treeList, map);
        if (treeList.isEmpty()){
            //非tree结构返回
            return baseBeanList;
        }
        return treeList;
    }


    //建立树形结构
    public static List<TreeBaseBean> treeList(List<? extends TreeBaseBean> allList, String pid) {
        Map<String, List<TreeBaseBean>> map = new HashMap<String, List<TreeBaseBean>>();
        List<TreeBaseBean> baseBeanList = new ArrayList<>();
        for(TreeBaseBean t : allList) {
            baseBeanList.add(t);
            String key = t.getParentId();
            if(map.containsKey(key)) {
                map.get(key).add(t);
            } else {
                List<TreeBaseBean> mapValue = new ArrayList<TreeBaseBean>();
                mapValue.add(t);
                map.put(key, mapValue);
            }
        }
        List<TreeBaseBean> tree = map.get(pid);
        recursionToTree(tree, map);
        if (tree==null){
            //非tree结构返回
            return baseBeanList;
        }
        return tree;
    }


    /**
     * 查找一个tree下面的全部叶子路径
     * @param rootTree
     * @return 叶子路径的集合
     */
    public static List<List<TreeBaseBean>> bfsTree(TreeBaseBean rootTree) {
        List<List<TreeBaseBean>> result = new ArrayList<>();
        Queue<TreeBaseBean> nodeQueue = new LinkedList<>();
        Queue<List<TreeBaseBean>> qstr = new LinkedList<>();
        nodeQueue.add(rootTree);
        ArrayList<TreeBaseBean> arrayList = new ArrayList<>();
        qstr.add(arrayList);
        while (!nodeQueue.isEmpty()) {
            TreeBaseBean curNode = nodeQueue.remove();
            List<TreeBaseBean> curList = qstr.remove();
            if (curNode.getChildren() == null || curNode.getChildren().size() <= 0) {
                curList.add(curNode);
                result.add(curList);
            } else {
                for (int i = 0; i < curNode.getChildren().size(); i++) {
                    TreeBaseBean treeNode = curNode.getChildren().get(i);
                    nodeQueue.add(treeNode);
                    List<TreeBaseBean> list = new ArrayList<>(curList);
                    list.add(curNode);
                    qstr.add(list);
                }
            }
        }
        return result;
    }



    //建立子树形结构
    private static void recursionToTree(List<TreeBaseBean> list, Map<String, List<TreeBaseBean>> map){
        if (map==null ||list==null){
            return;
        }
        for(TreeBaseBean t : list){
            Object key = t.getId();
            if(map.containsKey(key)) {
                List<TreeBaseBean> children = map.get(key);
                t.setChildren(children);
                recursionToTree(children, map);
            }
        }
    }
}
